package com.ddd.demo.test;

/**
 *
 * 首先通过外层的for循环，从数组的第二个元素（索引为1）开始遍历整个数组，
 * 这里索引i表示当前要插入到已排序部分的元素位置。每次循环取出当前位置的元素key（也就是要插入的元素）。
 *
 * 接着通过内层的while循环，从已排序部分的最后一个元素（索引为i - 1）开始向前比较，如果发现已排序部分的元素大于key，
 * 就将这个较大的元素往后移动一位（即arr[j + 1] = arr[j];），同时索引j减1继续向前比较，直到找到合适的位置（即arr[j] <= key或者j小于0了）。
 *
 */
public class InsertSort {

    public static void main(String[] args) {

        Integer[] arr = new Integer[]{2, 3, 1, 4, 5};
        iSort(arr);

    }

    private static void iSort(Integer[] arr) {
        int length = arr.length;
        for (int i = 1; i < length - 1; i++) {
            int base = arr[i];
            int j = i - 1;
            // 比base大的都要往后面移动
            while (j >= 0 && arr[j] > base) {

                arr[j + 1] = arr[j];

                j--;
            }
            arr[j + 1] = base;
        }
        for (int i = 0; i < length; i++) {
            System.out.println("arr[i] = " + arr[i]);
        }
    }


}
